import java.util.Arrays;

/**
 * @Question quickSort
 * @Date 2022/10/14 11:19
 * @Solution
 */
public class quickSort {
    static int count=0;
    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
        long cur = System.currentTimeMillis();
        quickSort(arr,0,arr.length-1);
        System.out.println(System.currentTimeMillis()-cur);
        System.out.println(Arrays.toString(arr)+count);
    }
    public static void quickSort(int arr[], int begin, int end) {
        count++;
        if(begin>end) {
            return;
        }
        int i=begin;
        int j=end;
        int target=arr[begin];
        while(i!=j) {
            while(i<j && target<=arr[j]) {
                j--;
            }
            while(i<j && target>=arr[i]) {
                i++;
            }
            if(i<j) {
                int tem = arr[i];
                arr[i] = arr[j];
                arr[j] = tem;
            }
        }
        arr[begin]=arr[i];
        arr[i]=target;
        quickSort(arr, begin, i-1);
        quickSort(arr,i+1,end);
    }
}
